package zhengqc.graph.algorithm;


import zhengqc.graph.data_structure.WeightedGraph;
import zhengqc.queue.PriorityQueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Node implements Comparable<Node> {
    public int vertex, distance;
    public Node(int vertex, int distance) {
        this.vertex = vertex;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node another) {
        return this.distance - another.distance;
    }
}

/* 适用于有权图, 有向图无向图都可 */
public class Dijkstra {
    private WeightedGraph graph;
    private int source;
    private int[] distances;
    private boolean[] visited;
    private int[] precedes;

    public Dijkstra(WeightedGraph graph, int source) {
        this.graph = graph;
        graph.validateVertex(source);
        this.source = source;
        this.distances = new int[graph.getV()];
        Arrays.fill(distances, Integer.MAX_VALUE);
        this.distances[source] = 0;
        this.precedes = new int[graph.getV()];
        Arrays.fill(this.precedes, -1);
        this.precedes[source] = source;
        // visited 永久标号集, 此时不能标记 source
        this.visited = new boolean[graph.getV()];

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.enqueue((new Node(source, 0)));
        while (!pq.isEmpty()) {
            int cur = pq.dequeue().vertex;
            if (this.visited[cur]) continue;
            this.visited[cur] = true; // 注意在此标记 cur 已被访问过
            for (int w: graph.getAdjacency(cur)) {
                if (!this.visited[w]) { // 如果 w 已经被访问过, 直接跳过
                    if (this.distances[cur]+this.graph.getWeighted(cur, w) < this.distances[w]) {
                        this.distances[w] = this.distances[cur] + this.graph.getWeighted(cur, w);
                        pq.enqueue(new Node(w, this.distances[w]));
                        this.precedes[w] = cur;
                    }
                }
            }
        }
    }

    public boolean isConnectedTo(int v) {
        this.graph.validateVertex(v);
        return this.visited[v];
    }

    public int getDistanceTo(int v) {
        this.graph.validateVertex(v);
        return this.distances[v];
    }

    public Iterable<Integer> getPathTo(int t) {
        ArrayList<Integer> result = new ArrayList<>();
        if (!isConnectedTo(t)) {
            return result;
        }
        int cur = t;
        while (cur != this.source) {
            result.add(cur);
            cur = this.precedes[cur];
        }
        result.add(this.source);
        Collections.reverse(result);
        return result;
    }
}
